The present disclosure relates to a methodology for rendering anti-aliased pixels in a digital image. More specifically, this disclosure relates to anti-aliased pixel identification and rendering via look-up table based edge detection.
Anti-aliasing in the context of digitizing line art and certain graphical image structures is best known as a method of using intermediate levels of intensity to achieve subpixel position of edges for several reasons including reduction or elimination of jaggies on the edges of lines and polygons, including text. As used herein the term anti-aliased is intended to refer to those segments or regions of an image that are effected by an anti-aliasing operation applied to the image (e.g. an image processing operation or a physical process resulting in gray pixels along the edges of line art or text). Jaggies are primarily visible at the edges of sloped lines approaching horizontal or vertical. The term anti-aliasing suggests an analog term aliasing, normally representing the presence of low frequencies resulting from sampling high frequency signals at too low a sampling rate.
Consider a near-vertical (or near-horizontal) line segment. To be perfectly reproduced in a printed media, the phase, which represents the location of the edge, must continuously vary along the length of a segment. Due to the inherent sampling of a bi-level display or printed output, the phase exhibits jump discontinuities. Thus, this form of aliasing artifact, leads to an induced jagged appearance where the structures are referred to jaggies. Within a sampled image any graphical object is eventually approximated as a polygon or collection of polygons. These polygons have straight edges some of which will exhibit aliasing (jaggies and other placement defects). FIG. 11 for example shows aliasing in two dimensions. When the triangle on the top of FIG. 11 is rasterized, the edges are aliased as reproduced in the triangle shown at the bottom of FIG. 11. In particular, the position along the bottom edge should move up slightly from column to column as one looks from left to right in the image at the bottom of FIG. 11. However, the position is quantized, as illustrated, producing the jagged appearance along the bottom of the triangle. Visibility of the anti-aliased image artifacts is increased by the regular nature of the jaggies, again a result of sampling.
Consider the following systems and their capability, or incapability, to utilize anti-aliased pixels. Xerox's Docucolor 40, for example, employs a high frequency analog line screen to render anti-aliased pixels, but that is not an option for some products or marked segments. When conventional screens (e.g., approximately equal to 130-150 CPI dots) are employed in a rendering module, anti-aliased pixels are halftoned and printed, resulting in objectionable halftone dots positioned along character edges. Hyperacuity printing techniques, for example those described by Curry, et al. (U.S. Pat. No. 5,138,339 and U.S. Pat. No. 5,485,289) can provide rendering for anti-aliased pixels which is compatible with simultaneously printing dot screen halftones in enhanced line art. However, these techniques require the use of tags to identify the anti-aliased pixels as anti-aliased line art.
Anti-aliased images can be generated by capturing the image at a resolution greater than the final or desired output resolution, then reducing the resolution of the image by sub-sampling using an averaging process. A major benefit of anti-aliased images is that high contrast, saturated objects are surrounded with pixels possessing intermediate values that visually suggest the true, higher resolution position of object edges.
For example, in binary printing systems, such as many xerographic or ink jet systems that use a halftoning process to simulate continuous tone images, these anti-aliased edge pixels should be rendered with a very high frequency cell, ideally one having the resolution of the final output image. If the standard system halftone dot were to be used, the anti-aliased edges would be serrated or jagged at the standard halftone frequency. This rendering would reduce or even negate any value obtained through anti-aliasing. The use of a very high frequency screen over the entire anti-aliased image renders the anti-aliased pixel properly, but tends to sharpen the tonal curve and provoke print quality defects in the overall image.
To optimally render anti-aliased pixels, it is beneficial to recognize pixels as anti-aliased or not anti-aliased. Since anti-aliasing primary affects pixels that are at the edges of image objects, recognition can be framed as a specific type of edge identification task.
An edge within an image is a sharp change in local intensity or lightness. In other words, edges are features within an image that possess strong intensity contrast. Edges occur between distinct objects in a scene, or within textures and structure within an object. For instance, typographic characters on a white page background produce distinct edges. Edge pixels in a digital image are those pixels that occur at and about an edge in the image.
Two key properties of an edge are strength and orientation. Edge strength is a measure of the contrast of an edge. A black typographic character on a white background produces stronger edges than a gray character on a white background. Edge orientation can be described by a variety of measures, such as angle quantified in degrees or by classes such as vertical, horizontal, and diagonal.
Other attributes of edges are also useful to image analysis and image processing. For instance, classification of combined edges, such as corners, has been used in object recognition and in image enhancement applications. Edge thickness is a measure that provides information on the breadth of a local contrast change and can indicate a degree of blur in an image, see for example: U.S. Pat. No. 6,763,141, entitled “ESTIMATION OF LOCAL DEFOCUS DISTANCE AND GEOMETRIC DISTORTION BASED ON SCANNED IMAGE FEATURES,” to inventors B. Xu, R. Loce, which is hereby incorporated in its entirety for its teachings. Inner edges and outer edges refer to regions just inside of or just outside of a given object, respectively, and have been used in applications such as character stroke thinning and thickening. The presence or absence of an edge is an edge-related property that has been used in applications such as image classification and recognition. Distance from an edge is also an edge-related property that has been used in image enhancement applications.
Edge detection in digital image processing typically employs a collection of methods used to identify or modify edge pixels or indicate properties of edges and edge pixels within an image. Edge detection methods are sometimes referred to simply as edge detectors. There are numerous applications of edge detectors in digital image processing for electronic printing. For example, identification of corner pixels has been used to sharpen corners within an image, see: U.S. Pat. No. 6,775,410, entitled “IMAGE PROCESSING METHOD FOR SHARPENING CORNERS OF TEXT AND LINE ART,” to inventors R. Loce, X. Zhu, C. Cuciurean-Zapan. Identification of inner and outer border pixels has been used to control the apparent darkness of character strokes, see: U.S. Pat. No. 6,606,420, entitled “METHOD AND APPARATUS FOR DIGITAL IMAGE DARKNESS CONTROL IN SATURATED IMAGE STRUCTURES”, to Loce et al; and U.S. Pat. No. 6,181,438, entitled “METHOD AND APPARATUS FOR DIGITAL IMAGE DARKNESS CONTROL USING QUANTIZED FRACTIONAL PIXELS,” to Bracco et al. Also identification of anti-aliased pixels has been used for preferred rendering of those same pixels, see: U.S. Pat. No. 6,243,499, entitled “TAGGING OF ANTIALIASED IMAGES,” to Loce, et al.; U.S. Pat. No. 6,144,461, entitled “METHOD FOR GENERATING RENDERING TAGS TO FACILITATE THE PRINTING OF ANTIALIASED IMAGES,” to Crean et al.; and U.S. Pat. No. 6,167,166, entitled “METHOD TO ENABLE THE RECOGNITION AND RENDERING OF ANTIALIASED IMAGES,” to Loce et al. All of the above cited are hereby incorporated by reference in their entirety for their teachings.
Edge detectors typically operate using a convolution mask and are based on differential operations. Differentials for edge/line detection are used to define color or brightness changes of pixels and their change directions. If there is an abrupt change of brightness within a short interval within an image, it means that within that interval there is high probability that an edge exists. One example of a convolution-based edge detector is the Roberts edge detector, which employs the square root of the magnitude squared of the convolution with the Robert's row and column edge detectors. The Prewitt edge detector employs the Prewitt compass gradient filters and returns the result for the largest filter response. The Sobel edge detector operates using convolutions with row and column edge gradient masks. The Marr-Hildreth edge detector performs two convolutions with a Laplacian of Gaussians and then detects zero crossings. The Kirsch edge detector performs convolution with eight masks that calculate gradient.
As indicated above, common edge detection methods employ a convolution-type computing architecture, usually with fixed coefficients. In the field of image processing, and in particular, for image processing in anticipation of electronic printing, the edge detection needs are numerous and varied. Further, image processing for electronic printing often requires that any processing method operate “real-time,” within a small number of fixed clock cycles, thereby excluding more complicated methods as too computationally intensive. What is needed is an anti-aliased pixel detection and rendering method with a computing architecture that is readily adapted to a wide variety of print and display settings. In particular, the anti-aliased pixel detection should be easily implementable in real-time and more adapted to the anti-aliased typography setting than are the common convolution-based methods of edge detection.
Disclosed in embodiments herein is an image processing method for rendering a digital image possessing anti-aliased pixels, comprising selecting a target pixel location within the digital image; observing a set of pixels within a pixel observation window superimposed on the digital image relative to the target pixel location; generating edge-state codes for a plurality of pairs of neighboring vectors of pixels within the pixel observation window; generating edge-identification codes from the plurality of edge-state codes using at least one look-up table; and, utilizing the edge-identification codes to select and apply to the digital image at the target pixel either anti-aliased rendering or conventional halftoning.
Further disclosed in embodiments herein is an image processing method for rendering anti-aliased pixels within a digital image, that comprises selecting a target pixel location within the digital image; observing a set of pixels within a pixel observation window superimposed on the digital image, relative to the target pixel location; generating edge-state codes for a plurality of pairs of neighboring vectors of pixels within the pixel observation window, wherein the plurality of vectors at of at least two different orientations; generating edge-identification codes from the plurality of edge-state codes using at least one look-up table; and, utilizing the edge-identification codes to select and apply anti-aliased rendering to the digital image at the target pixel.
Further disclosed in embodiments herein is a method for producing a rendered digital image using anti-aliased rendering and conventional halftoning, which comprises a) observing a set of pixels within a pixel observation window superimposed on the digital image relative to a target pixel location; b) generating edge-state codes for a plurality of pairs of neighboring vectors of pixels within the pixel observation window; c) generating edge-identification codes from the plurality of edge-state codes using at least one look-up table, wherein the edge-identification codes indicate proximity to a tinted edge; and, utilizing the edge-identification codes to select and apply to the digital image at the target pixel either anti-aliased rendering or conventional halftoning.